package com.zhupf.stack;

import java.util.*;

/**
 * @author zhupf
 * @date 2024年12月17日 16:00
 * @Description
 *  https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/description/
 *  1081. 不同字符的最小子序列
 *   返回 s 字典序最小的
 * 子序列
 * ，该子序列包含 s 的所有不同字符，且只包含一次。
 *
 *  示例 1：
 *
 * 输入：s = "bcabc"
 * 输出："abc"
 * 示例 2：
 *
 * 输入：s = "cbacdcbc"
 * 输出："acdb"
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s 由小写英文字母组成
 *
 */
public class SmallestSubsequence {

    public static void main(String[] args) {
        System.out.println(smallestSubsequence("bcabc"));
    }

    public static String smallestSubsequence(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Integer integer = map.get(c);
            map.put(c, integer == null ? 1 : integer + 1);
        }
        Deque<Integer> deque = new LinkedList<>();
        Set<Character> exists = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!exists.contains(c)) {
                while (!deque.isEmpty() && s.charAt(deque.peek()) >= s.charAt(i) && map.get(s.charAt(deque.peek())) > 1) {
                    Integer pop = deque.pop();
                    map.put(s.charAt(pop), map.get(s.charAt(pop)) - 1);
                    exists.remove(s.charAt(pop));
                }
                deque.push(i);
                exists.add(s.charAt(i));
            } else {
                map.put(c, map.get(c) - 1);
            }
        }
        StringBuffer sb = new StringBuffer();
        while (!deque.isEmpty()) {
            sb.append(s.charAt(deque.pollLast()));
        }
        return sb.toString();
    }

}
